package com.s10.tree;

import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTree {

	private TreeNode rootNode;

	public void insert(int data) {
		this.insert(createNode(data));
	}

	protected void insert(TreeNode newNode) {
		if (this.rootNode == null) {
			this.rootNode = newNode;
			return;
		}

		TreeNode p = this.rootNode;
		while (p != null) {
			// 比中间节点小
			if (newNode.data < p.data) {
				if (p.left == null) {
					p.left = newNode;
					break;
				}
				p = p.left;
			}
			// 比中间节点大
			else {
				if (p.right == null) {
					p.right = newNode;
					break;
				}
				p = p.right;
			}
		}
	}

	// 我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找。反之去右子树进行寻找
	public TreeNode find(int data) {
		TreeNode p = this.rootNode;
		while (p != null) {
			if (data == p.data) {
				return p;
			}
			if (data < p.data) {
				p = p.left;
			} else {
				p = p.right;
			}
		}
		return null;
	}

	// 删除操作就比较复杂 。针对要删除节点的子节点个数的不同，分三种情况来处理
	public boolean delete(int data) {
		boolean isFind = false;
		TreeNode parentOfP = null;
		TreeNode p = this.rootNode;
		while (p != null) {
			if (data == p.data) {
				isFind = true;
				break;
			}
			parentOfP = p;
			if (data < p.data) {
				p = p.left;
			} else {
				p = p.right;
			}
		}

		// 没有找到返回 null
		if (p == null) {
			return false;
		}

		// 要删除的节点有两个子节点
		if (p.left != null && p.right != null) {
			// 找寻 q 右侧的最小左叶子节点 n, n 替换掉 q 的位置，并删除 最小左叶子节点（前驱节点的 next 置为 null）
			TreeNode parentOfMinP = p;
			TreeNode minP = p.right;
			while (minP != null && minP.left != null) {
				parentOfMinP = minP;
				minP = minP.left;
			}
			if (true) {
				// 方案一：从删除 p 节点的问题 转移为 删除 minP 节点的问题
				p.data = minP.data;
				deleteNodeByParent(minP, parentOfMinP);
			} else {
				// 方案二：删除节点 p， minP 移动到 p 的位置
				deleteChildNodeByMinP(p, parentOfMinP, minP);
			}
		} else {
			deleteNodeByParent(p, parentOfP);
		}
		return isFind;
	}

	// node 是当前要删除的节点, parentOfMinP 是 p 右子树的最小节点的父节点, minP 是 p 右子树的最小节点
	private void deleteChildNodeByMinP(TreeNode node, TreeNode parentOfMinP,
			TreeNode minP) {
		// 说明 q.right 即是最小值
		if (node.right == minP) {
			// 根节点
			minP.left = node.left;
		} else {
			// minP 节点肯定没有左子树, 即 minP.left = null;
			// 移除 minP 节点
			if (parentOfMinP.left == minP) {
				parentOfMinP.left = minP.right;
			} else {
				parentOfMinP.right = minP.right;
			}
			// minP 节点 替换 原来的 p 节点
			minP.left = node.left;
			minP.right = node.right;
		}
		node.left = null;
		node.right = null;
		// 根节点
		if (node == this.rootNode) {
			this.rootNode = minP;
		}
	}

	// 至少一个节点为空: 删除节点是叶子节点或者仅有一个子节点
	private void deleteNodeByParent(TreeNode node, TreeNode parent) {
		TreeNode childNode = node.left != null ? node.left : node.right;
		// 删除的是根节点
		if (parent == null) {
			this.rootNode = childNode;
		} else {
			if (parent.left == node) {
				parent.left = childNode;
			} else {
				parent.right = childNode;
			}
		}
	}

	public TreeNode findMin() {
		TreeNode p = this.rootNode;
		while (p != null && p.left != null) {
			p = p.left;
		}
		return p;
	}

	public TreeNode findMax() {
		TreeNode p = this.rootNode;
		while (p != null && p.right != null) {
			p = p.right;
		}
		return p;
	}

	public void foreach() {
		foreach(this.rootNode);
	}

	// 先序遍历 中->前->后 1 2 4 5 3 6 7
	static void qian(TreeNode p) {
		if (p != null) {
			System.out.print(p.data + " ");
			qian(p.left);
			qian(p.right);
		}
	}

	// 中序遍历 前 中 后 4 2 5 1 6 3 7
	static void zhong(TreeNode p) {
		if (p != null) {
			zhong(p.left);
			System.out.print(p.data + " ");
			zhong(p.right);
		}
	}

	// 后序遍历 前 后 中 4 5 2 6 7 3 1
	static void hou(TreeNode p) {
		if (p != null) {
			hou(p.left);
			hou(p.right);
			System.out.print(p.data + " ");
		}
	}

	// 按层遍历
	static void foreach(TreeNode node) {
		System.out.println("foreach [");
		if (node != null) {
			Queue<TreeNode> queue = new LinkedList<>();
			queue.add(node);

			while (!queue.isEmpty()) {
				int size = queue.size();
				for (int i = 0; i < size; i++) {
					TreeNode removedNode = queue.remove();
					System.out.print(removedNode.data + " ");

					if (removedNode.left != null) {
						queue.add(removedNode.left);
					}
					if (removedNode.right != null) {
						queue.add(removedNode.right);
					}
				}
				System.out.println();
			}
		}
		System.out.println("]");
	}

	protected TreeNode createNode(int data) {
		return new TreeNode(data);
	}

	static final class TreeNode {

		public Integer data;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int data) {
			this.data = data;
		}

		@Override
		public String toString() {
			return "[node: data = " + this.data + "]";
		}
	}
}
